package sort;

import java.util.Arrays;

/**
 * 归并排序
 */
public class MergeSort {

  public static void main(String[] args) {

    int[] array={9,5,3,7,12,8,0,11,56,34};
    int[] temp=new int[array.length];
    mergeSort(array,temp,0,array.length-1);
    System.out.println(Arrays.toString(array));
  }

  private static void mergeSort(int[] array, int[] temp,int left,int right) {
    if (left<right){//一个元素无需排序
      int mid=(left+right)/2;
      mergeSort(array,temp,left,mid);
      mergeSort(array,temp,mid+1,right);
      merge(array,temp,left,mid,right);
    }
  }

  private static void merge(int[] array, int[] temp, int left, int mid, int right) {
    int l=left;
    int r=mid+1;
    int pos=left;
    while (l<=mid&&r<=right){
      if (array[l]<=array[r]){
        temp[pos]=array[l];
        l++;
      }else {
        temp[pos]=array[r];
        r++;
      }
      pos++;
    }
    //合并左半区剩余元素
    while (l<=mid){
      temp[pos++]=array[l++];
    }
    //合并右半区剩余元素
    while (r<=right){
      temp[pos++]=array[r++];
    }
    //将临时数组复制给原数组
    while (left<=right){
      array[left]=temp[left];
      left++;
    }

  }

}
